6. Z字形变换

一、题目原型：

将字符串 “PAYPALISHIRING” 以Z字形排列成给定的行数：
输入: s = “PAYPALISHIRING”, numRows = 3
输出: “PAHNAPLSIIGYIR”
输入: s = “PAYPALISHIRING”, numRows = 4
输出: “PINALSIGYAHRPI”
实现一个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);

二、题目意思剖析：

numRows = 3
P   A   H   N
A P L S I I G
Y   I   R

numRows = 4
P      I       N
A   L  S    I  G
Y A    H  R
P      I

三、解题思路：

3.1. 将原字符串按照“z字转换规律”保存进一个二维数组

3.2.将该二维数组横竖对调，得到最后的二维数组

3.3.用字符串拼接得到最后的答案

核心思路：找规律，找关键的几个数据和numRows、字符串总长度之间的关系。
下图中方框内表示一个单元格。
笔记思路

第一步：能够看出，这个排列是由一个个单元格(相同的排列)组成。

 P      I       N
 A   L  S    I  G
 Y A    H  R
 P      I
其中，单元格是
 P
 A   L
 Y A
 P

第二步：算出每一个单元所包含的字符个数

很简单可以看出，每个单元是由最长的那一列+中间的那几个字符。
而中间那些字符，刚好是除去最上面和最下面的那些。
所以：

1	let letterCount = numRows + (numRows - 2)

第三步：每个单元格包含的列数

1表示是行数最大那一列，(numRows - 2)是中间过渡的那几列

1	let cols: Int = 1 + (numRows - 2)

第四步：总共有多少个单元格

var count: Int = 0
while letterCount*count <= letters.count {
    
    count = count + 1
}
// 因为最后count会再次累加1，所以需要减1.
count = count - 1

第五步：总共列数

// 最终列数
var allCols: Int = 0
// 余数：比如字符长度为17，17 % 6 = 5
let remainder = letters.count % letterCount
if remainder == 0 { // 说明刚好有整数个单元格
    allCols = count * cols
}else if remainder >= numRows && remainder < letterCount { 
    //如果余数大于或者行数，并且小于一个单元格所包含的最大字符数，allCols = 前面整数个的单元格列数 + 1 + (余数 - numRows)
    allCols = count * cols + 1 + (remainder - numRows)
}else {
    // 比如上面的例子， PAYPALISHIRING中，结果余数 = 14%6 = 2，2 < numRows，所以allCols =  前面整数个的单元格列数 + 1
    allCols = count * cols + 1
}

// 1.前二维数组
var allConvert = dim(allCols, dim(numRows, "*"))
var index: Int = 0 // 总字符串索引
for i in 0..<allCols {
    // i % cols，余数 - 指的是字母离底部多长。
    if i % cols == 0 { // 当余数为0时，就是最长列的时候。
        var convert: [String] = Array.init(repeating: "*", count: numRows)
        var j: Int = 0
        while index < letterCount * (i/cols + 1) && index < letters.count && j < numRows {
            convert[j] = letters[index]
            allConvert[i] = convert
            index = index + 1
            j = j + 1
        }
    }else { // 其他时候，就是用（ 最大行数 - 1 - 余数 ）
        var convert: [String] = Array.init(repeating: "*", count: numRows)
        convert[numRows - 1 - i%cols] = letters[index]
        allConvert[i] = convert
        index = index + 1
    }
}
print(allConvert)

这里需要一个创建二维数组的函数

// 创建二维数组
func dim<T>(_ count: Int, _ value: T) -> [T] {
    return [T](repeating: value, count: count)
}

第六步：横竖置换

[["a", "b", "c", "d"],
 ["*", "*", "e", "*"],
 ["*", "f", "*", "*"],
 ["g", "h", "i", "j"],
 ["*", "*", "k", "*"],
 ["*", "l", "*", "*"]]
         变成
 [["a", "*", "*", "g", "*", "*"],
 ["b", "*", "f", "h", "*", "l"],
 ["c", "e", "*", "i", "k", "*"],
 ["d", "*", "*", "j", "*", "*"]]

// 将数组横转，横 -> 竖
// i[0,6) j[0,4)  ->   i[0,4) j[0,6)
var resultConverts = dim(numRows, dim(allCols, "*"))
for i in 0..<allCols {
    for j in 0..<numRows {
        resultConverts[j][i] = allConvert[i][j]
    }
}

第七步：拼接最终字符串

var result: String = ""
for i in 0..<numRows {
    for j in 0..<allCols {
        if resultConverts[i][j] != "*" {
            result.append(resultConverts[i][j])
        }
    }
}
print(resultConverts)
// result就是我们需要的答案